#include <unordered_set>
using namespace std;
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
bool hasCycle(ListNode *head) {
  unordered_set<ListNode *> set;
  while (head != nullptr) {
    if (set.count(head) == 1) {
      return true;
    }
    set.insert(head);
    head = head->next;
  }
  return false;
}

// 双指针解法
bool hasCycle_(ListNode *head) {
  if (head == nullptr) {
    return false;
  }
  ListNode *q = head, *s = head;
  while (q != nullptr) {
    for (int i = 0; i < 2; i++) {
      if (q->next == nullptr) {
        return false;
      }
      q = q->next;
    }
    s = s->next == nullptr ? nullptr : s->next;
    if (q == s) {
      if (q->next != nullptr) {
        return true;
      } else {
        return false;
      }
    }
  }
  return false;
}